The present invention relates generally to the field of database systems. More particularly, the present invention relates to the field of sampling records in a database system.
Computer database systems manage the storage and retrieval of data in a database. A database comprises a set of tables of data along with information about relations between the tables. Tables represent relations over the data. Each table comprises a set of records or tuples of data stored in one or more data fields. The records of a table are also referred to as rows, and the data fields of records in a table are also referred to as columns. A database server processes data manipulation statements or queries, for example, to retrieve, insert, delete, and update data in a database. Queries are defined by a query language supported by the database system.
For large databases such as data warehouses, for example, typical tools such as On Line Analytical Processing (OLAP) and data mining serve as middleware or application servers that communicate data retrieval requests to a backend database system through a query. Although the cost of executing ad-hoc queries against the backend can be expensive, many data mining applications and statistical analysis techniques can use a sample of the data requested through the query. Similarly, OLAP servers that answer queries involving aggregation (e.g., xe2x80x9cfind total sales for all products in the NorthWest region between Jan. 1, 1998 and Jan. 15, 1998xe2x80x9d) benefit from the ability to present to the user an approximate answer computed from a sample of the result of the query posed to the database.
Sampling is preferably supported not only on existing stored or base relations but also on relations produced as a result of an arbitrary query. Samping may be supported in relational databases as a primitive operation SAMPLE(R,f), for example, to produce a sample S of r tuples that is an f-fraction of a relation R. Fully evaluating a query Q to compute relation R only to discard most of relation R when applying SAMPLE(R,f), however, is inefficient. Preferably, query Q may be partially evaluated so as to produce only sample S of relation R.
For a given query tree T for computing a relation R that is the result of a query Q where SAMPLE(R,F) is the root or last operation of query tree T, pushing the sample operation down tree T toward its leaves would help minimize the cost of evaluating query Q as only a small fraction of stored and/or intermediate relations would be considered in evaluating query Q. The ability to commute the sample operation in this manner, however, depends on the relational operations used in query tree T. The standard relational operation of selection can be freely interchanged with sampling. With join operations, however, sampling may not be so easily commuted.
FIG. 1 illustrates a query tree 100 for obtaining a sample of a join of operand relations R1 and R2. Query tree 100 is executed in accordance with a flow diagram 200 of FIG. 2. For step 202 of FIG. 2, a relation J is computed by joining R1 and R2, or J=R1∞R2. For step 204, r tuples are randomly sampled from relation J to produce a sample relation S. Commuting the sample operation in query tree 100 to operand relations R1 and R2, as illustrated by a query tree 300 in FIG. 3, would minimize the cost of obtaining a join sample because only samples of operand relations R1 and R2 would need to be joined. A join of samples of operand relations R1 and R2, however, will not likely give a random sample of the join of operand relations R1 and R2.
As one example:
R1(A,B)={(a1,b0), (a2,b1), (a2,b2), (a2,b3), . . . , (a2,bn)}
and
xe2x80x83R2(A,C)={(a2,c0), (a1,c1), (a1,c2), (a1,c3), . . . , (a1,cn)}.
That is, relation R1 is defined over attributes A and B. Among the n+1 tuples of relation R1, one tuple has an A-value a1 and n tuples have an A-value a2, but all n+1 tuples of relation R1 have distinct B-values. Similarly, relation R2 is defined over attributes A and C. Among the n+1 tuples of relation R2, n tuples have an A-value a1 and one tuple has an A-value a2, but all n+1 tuples of relation R2 have distinct C-values.
Computing the equi-join of relations R1 and R2 over attribute A produces the following relation:
J=R1∞R2={(a1,b0,c1), (a1,b0,c2), (a1,b0,c3), . . . , (a1,b0,cn), (a2,b1,c0), (a2,b2,c0), (a2,b3,c0), . . . , (a2,bn,c0)}.
That is, relation J has n tuples with A-value a1 and n tuples with A-value a2.
About one half of the tuples in a random sample S of relation J, or S⊂J, would likely have an A-value of a1 while the remaining tuples would have an A-value of a2. A random sample S1 of relation R1, or S1⊂R1, however, would not likely comprise tuple (a1,b0), and a random sample S2 of relation R2, or S2⊂R2, would not likely comprise tuple (a2,c0). The join of samples S1 and S2 would then likely comprise no tuples and therefore would not likely give random sample S of relation J.
One prior sampling strategy for obtaining a sample S of a join of two relations R1 and R2 with respect to a join attribute A is illustrated as a flow diagram 400 in FIG. 4.
For notational purposes, relations R1 and R2 have sizes n1 and n2, respectively. The domain of join attribute A is denoted by D. For each value v of domain D, or vxcex5D, m1(v) and m2(v) denote the number of distinct tuples in relations R1 and R2, respectively, that contain value v in attribute A. Then, xcexa3vxcex5D m1(v)=n1 and xcexa3vxcex5D m2(v)=n2. A relation J results from the computation of the join of relations R1 and R2, or J=R1∞R2, and n is the size of relation J, or n=|J|=|R1∞R2|. Then, n=xcexa3vxcex5D m1(v)m2(v). For each tuple t of relation R1, the set of tuples in relation R2 that join with tuple t is denoted as Jt(R2)={txe2x80x2xcex5R2|txe2x80x2.A=t.A}; t∞R2 denotes the set of tuples in R1∞R2 obtained by joining tuple t with the tuples in Jt(R2); and |t∞R2|=|Jt(R2)|=m2(t.A). Similarly for each tuple t of relation R2, Jt(R1)={txe2x80x2∞R1|txe2x80x2.A=t.A}; R1∞t denotes the set of tuples in R1∞R2 obtained by joining tuples in Jt(R1) with tuple t; and |R1∞t|=|Jt(R1)|=m1(t.A).
For step 402 of FIG. 4, a variable r is initialized to the size of a sample relation S to be obtained from the join of relations R1 and R2. For step 404, a variable M is initialized to the upper bound on the number of join attribute values v in relation R2 for all values v of domain D on attribute A. That is, M is the maximum number of any one join attribute value in relation R2. A tuple t1 is randomly sampled from relation R1 for step 406. A tuple t2 is then randomly sampled for step 408 from among all tuples of relation R2 having a join attribute value t2.A that matches the join attribute value t1.A of tuple-t1. For step 410, a tuple T is computed as T=t1∞t2 and output for sample relation S with a probability based on the number of tuples in relation R2 having a join attribute value that matches that of tuple t1 divided by M, or m2(t2.A)/M. If not output, the sample tuple t1 is rejected for step 410. If r tuples have not yet been output for sample relation S as determined for step 412, steps 406 through steps 412 are then repeated until r tuples have been output to form sample relation S as determined for step 412. Flow diagram 400 then ends for step 414.
The sampling technique of FIG. 4 in practice, however, requires indexes for random access to relations R1 and R2, noting relation R1 must be materialized for proper sampling because the rejection of tuples for step 410 requires that the number of samples from relation R1 be a random variable.having a distribution dependent upon the distribution of join attribute values in relation R2. This strategy therefore has limited applicability in commuting sampling with joins involving intermediate relations that are produced as a result of an arbitrary query in a query tree and that are not materialized and indexed.
The ability to sample tuples produced as a stream, that is to perform sequential sampling, is significant not only because intermediate relations produced by a pipeline, such as in a query tree for example, may be sampled without materialization but also because a relation, whether materialized or not, may be sampled in a single pass. How and whether sequential sampling may be performed, however, may depend on the chosen semantics for the sampling.
The tuples of a relation may be sampled, for example, using with replacement (WR), without replacement (WoR), or independent coin flips (CF) semantics.
For WR sampling of an f-fraction of the n tuples in a relation R, each sampled tuple is chosen uniformly and independently from among all tuples in relation R, noting any one tuple could be sampled multiple times. The sample is a bag or multiset of f*n tuples from relation R.
For WoR sampling an f-fraction of the n tuples in a relation R, f*n distinct tuples are sampled from relation R, noting each successive sampled tuple is chosen uniformly from the set of tuples not yet sampled. The sample is a set of f*n distinct tuples from relation R.
For CF sampling an f-fraction of the n tuples in a relation R, each tuple in relation R is chosen for the sample with probability f, independent of other tuples. Sampling in this manner is analogous to flipping a coin with bias f for each tuple in turn. The sample is a set of X distinct tuples from relation R, where X is a random variable with the binomial distribution B(n,f) and has expectation f*n. The binomial distribution B(n,f) is, in effect, the distribution of a random value generated by counting the total number of heads when flipping n independent coins, each of which has a probability f of being heads. Sampling using independent coin flip semantics is also called binomial sampling.
The sampling of a relation may also be weighted or unweighted. For unweighted sampling, each element is sampled uniformly at random. For weighted sampling, each element is sampled with a probability proportional to its weight for some pre-specified set of weights.
One prior sequential sampling technique uses CF semantics by sampling each passing tuple of a relation R with probability f for heads and adds the tuple to a sample S if the probability is satisfied. Another prior sequential sampling technique uses WoR semantics by initializing a list or reservoir of r tuples with the first r tuples of relation R and repeatedly removing random tuples from the list while adding tuples from relation R to the end of the list to produce a sample S. Each of these techniques do not require the size of relation R in advance and may therefore be used for sampling relations that are not materialized. Each of these techniques also preserve sortedness by producing a sample of tuples in the same relative order as in relation R. The reservoir sampling technique, however, does not produce a sequential output of tuples as no tuples are output until the technique has terminated. In the case of scanning a materialized relation on a disk, however, the reservoir sampling technique may be efficient by reading only those tuples to be entered in the reservoir by generating random intervals of tuples to be skipped.
A join sample operator for obtaining a sample of a join of first and second relations of records in a database system has the first and second relations as parameters. The join sample operator may also have a size of the sample as a parameter and/or sampling semantics as a parameter. The sampling semantics may be with replacement, without replacement, or coin flip sampling semantics.
A method obtains a sample of a join in a database system. The method may be implemented by computer-executable instructions of a computer readable medium.
For the method, first and second relations of records are identified from parameters of a join sample operator, and a sample of a join of the identified first and second relations is obtained. A size of the sample to be obtained may also be identified from a parameter of the join sample operator, and the sample of the join of the identified first and second relations may be obtained based on the identified sample size. Sampling semantics may be identified from a parameter of the join sample operator, and the sample of the join of the identified first and second relations may be obtained in accordance with the identified sampling semantics. The identified sampling semantics may be with replacement, without replacement, or coin flip sampling semantics.
The sample of the join of the first and second relations may be obtained by sampling records of the first relation based on join attribute values of the second relation to obtain a first sample of records and joining one or more records of the first sample with one or more records of the second relation. The sample of the join of the first and second relations may also be obtained by sampling records of the first relation having a matching join attribute value with at least a predetermined number of records in the second relation to obtain a first sample of records, joining the records of the first sample with the records of the second relation, joining records of the first relation having a matching join attribute value with less than the predetermined number of records in the second relation with the records of the second relation, and obtaining the sample of the join of the first and second relations from the joined records of the first sample and second relation and from a sample of the other joined records.
Another method obtains a sample of a join of first and second relations of records in a database system. The method may be implemented by computer-executable instructions of a computer readable medium. The database system may perform the method with suitable means.
For the method, records of the first relation are sampled based on join attribute values of the second relation to obtain a first sample of records, and one or more records of the first sample are joined with one or more records of the second relation.
Records of the first relation may be sampled based on the number of records having a matching join attribute value in the second relation and/or based on a weight specified for each record of the first relation based on the number of records having a matching join attribute value in the second relation. Frequency statistics on join attribute values of the second relation may be used to sample records of the first relation.
The first relation may be produced as a stream of records as a result of a query or may be a base relation materialized in a database of the database system. Records of the first relation may be sampled using a with replacement, without replacement, or coin flip sampling technique and/or may be sampled in one pass using a sequential sampling technique.
Records of the first relation may be sampled by selectively outputting a record of the first relation one or more times based on a probability and repeating this step for each record of the first relation. Records of the first relation may also be sampled by initializing a reservoir of records, selectively resetting one or more records of the reservoir to be a record of the first relation based on a probability, repeating this just prior step for each record of the first relation.
One or more records of the first sample may be joined with one or more records of the second relation by sampling a record from the second relation having a matching join attribute value with an identified record of the first sample and joining the identified record of the first sample with the sampled record of the second relation. These steps may be repeated for each record of the first sample.
One or more records of the first sample may also be joined with one or more records of the second relation by joining the records of the first sample with the records of the second relation to produce a relation having groups of records with each group corresponding to a respective one of the records of the first sample. One record from each group may then be sampled.
One or more records of the first sample may also be joined with one or more records of the second relation by sampling records from the second relation to obtain a second sample of records such that the number of records in the first sample with any one join attribute value is the same as that in the second sample and joining the records of the first sample with the records of the second sample. The records of the first sample may be joined with the records of the second sample by sampling a record without replacement from the first sample having a matching join attribute value with an identified record of the second sample, joining the sampled record of the first sample with the identified record of the second sample, and repeating these steps for each record of the second sample.
Records of the first relation having a matching join attribute value with at least a predetermined number of records in the second relation may be sampled to form the first sample, and the records of the first sample may be joined with the records of the second relation. Records of the first relation having a matching join attribute value with less than the predetermined number of records in the second relation may be joined with the records of the second relation. The sample of the join of the first and second relations maybe obtained from the joined records of the first sample and second relation with a probability based on the number of records that would result from joining the records of the first relation having a matching join attribute value with at least the predetermined number of records in the second relation with the records of the second relation and from a sample of the other joined records with a probability based on the number of records that would result from joining the records of the first relation having a matching join attribute value with less than the predetermined number of records in the second relation with the records of the second relation.